#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define OK 1
#define OVERFLOW -2
typedef struct Node
{
    int coef;
    int index;
    Node * next;
}Node, *LinkList;
typedef int Status;
Status InitPoly(LinkList &L)
{
    L = (LinkList)malloc(sizeof(Node));
    if (!L)
        exit(OVERFLOW);
    L->next = NULL;
    L->coef = 0;
    L->index = 0;

    return OK;
}
Status setPoly(LinkList &L)
{
    int total = 0;
    printf("输入节点个数：\n");
    scanf("%d", &total);
    int co, in;
    LinkList pt = L;
    for (int i = 0; i < total; ++i)
    {
        printf("输入第%2d个系数和指数\n", i+1);
        scanf("%d%d", &co, &in);
        LinkList p = (LinkList)malloc(sizeof(Node));
        if (!p)
            exit(OVERFLOW);
        p->coef = co;
        p->index = in;
        pt->next = p;
        pt = p;
    }
    pt->next = NULL;

    return OK;
}
Status deal_zero(LinkList &L);
Status addPoly(LinkList L1, LinkList L2, LinkList &L3)
{
    LinkList p1 = L1->next;
    LinkList p2 = L2->next;
    LinkList p3 = L3;
    while (p1 && p2)
    {
        LinkList p = (LinkList)malloc(sizeof(Node));
        if (p1->index > p2->index)
        {
            p->coef = p2->coef;
            p->index = p2->index;
            p2 = p2->next;
        }
        else if (p1->index < p2->index)
        {
            p->coef = p1->coef;
            p->index = p1->index;
            p1 = p1->next;
        }
        else // the index of p1 is equal to that of p2
        {
            p->coef = p1->coef + p2->coef;
            p->index = p1->index;
            p1 = p1->next;
            p2 = p2->next;
        }
        p3->next = p;
        p3 = p;
    }
    if (p1)
    {
        while (p1)
        {
            LinkList p = (LinkList)malloc(sizeof(Node));
            p->coef = p1->coef;
            p->index = p1->index;
            p3->next = p;
            p3 = p;
            p1 = p1->next;
        }
        p3->next = NULL;
    }
    else // p2
    {
        while (p2)
        {
            LinkList p = (LinkList)malloc(sizeof(Node));
            p->coef = p2->coef;
            p->index = p2->index;
            p3->next = p;
            p3 = p;
            p2 = p2->next;
        }
        p3->next = NULL;
    }
    deal_zero(L3);
    return OK;
}
Status multiplyPoly(LinkList L1, LinkList L2, LinkList &L3)
{
    LinkList p1 = L1->next;
    while (p1)
    {
        LinkList p2 = L2->next;
        while (p2)
        {
            int co = p1->coef * p2->coef;
            int in = p1->index + p2->index;
            LinkList pre = L3, cur = L3->next;
            bool newflag = true; // 是否要新建节点
            while (cur)
            {
                if (in == cur->index)
                {
                    cur->coef += co;
                    newflag = false;
                    break;
                }
                if (in < cur->index) // 这里写小于则升序，写大于则降序
                    break;
                pre = cur;
                cur = cur->next;
            }
            if (newflag)
            {
                LinkList newnode = (LinkList)malloc(sizeof(Node));
                newnode->coef = co;
                newnode->index = in;
                newnode->next = pre->next;
                pre->next = newnode;
            }
            p2 = p2->next;
        }
        p1 = p1->next;
    }
    deal_zero(L3);
    return OK;
}
Status deal_zero(LinkList &L)
{
    LinkList pre = L, cur = L->next;
    while (cur)
    {
        if (cur->coef == 0)
        {
            LinkList p = cur;
            pre->next = p->next;
            free(p);
            p = NULL;
            cur = pre->next;
        }
        else
        {
            pre = cur;
            cur = cur->next;
        }
    }
    return OK;
}
void printf_node(LinkList p);
void showPoly(LinkList L)
{
    LinkList p = L->next;
    printf_node(p);
    p = p->next;
    while (p)
    {
        if (p->coef > 0)
            printf("+");
        printf_node(p);
        p = p->next;
    }
    printf("\n");
}
void printf_node(LinkList p)
{
    // 先输出系数 1省略 -1省略1 其他正常输出
    if (p->coef == -1)
        printf("-");
    else if (p->coef != 1)
        printf("%d", p->coef);
    // 输出x
    printf("x");
    // 输出系数 1省略^1 其他正常输出
    if (p->index != 1)
        printf("^%d", p->index);
}
/*
多项式加法输入系数与指数时，以指数为关键字，依次递增输入
多项式乘法输入系数与指数时，可任意输入
输出结果若系数为1和-1，则省略1；若指数为1，则省略指数
输出结果首项若为正，则省略+
最后输出结果均以指数为关键字，递增输出
*/
int main(void)
{
    LinkList L1, L2, L3, L4;
    InitPoly(L1);
    InitPoly(L2);
    InitPoly(L3);
    InitPoly(L4);

    setPoly(L1);
    setPoly(L2);
    showPoly(L1);
    showPoly(L2);

    addPoly(L1, L2, L3);
    showPoly(L3);

    multiplyPoly(L1, L2, L4);
    showPoly(L4);

    return 0;
}
// 2  1 2  1 3    2  1 10  1 20
// 2  1 2  1 3    2  -1 2  1 20
// 2  1 1  1 3    2  -1 2  1 20